1. Field of the Invention
The present invention relates to a method for elliptic curve scalar multiplication, and more particularly, to methods of modifying or manipulating an elliptic curve cryptographic key to render the encryption resistant to power analysis attacks, and to software, smart cards, circuits, processors, or application specific integrated circuits (ASICs) designed to carry out the method.
2. Description of the Related Art
Elliptic Curve Cryptosystems (ECC), originally proposed by Niel Koblitz and Victor Miller in 1985, offer a serious alternative to earlier public key cryptosystems, such as Rivest-Shamir-Adleman (RSA) and ElGamal, with much shorter key size. To date, no significant breakthroughs have been made in determining weaknesses in the ECC algorithm, which is based on the discrete logarithm problem over points on an elliptic curve. The fact that the problem appears so difficult to crack means that key sizes can be reduced considerably, even exponentially. This has caused ECC to become a serious challenger to RSA and ElGamal cryptosystems. Because of these advantages, ECC have been recently incorporated in many standards. ECC have gained popularity for cryptographic applications because of the short key, and are considered to be particularly suitable for implementation on smart cards or mobile devices.
Power analysis attacks on such devices are considered serious threats due to the physical characteristics of these devices and their use in potentially hostile environments. Power analysis attacks seek to break the security of these devices through observing their power consumption trace or the timing of computations. Careless or naive implementations of cryptosystems may allow power analysis attacks to infer the secret key or obtain partial information about the secret key. Thus, designers of such systems seek to introduce algorithms that are not only efficient, but also resistant to power analysis attack.
An elliptic curve over a finite field GF(q) defines a set of points (x,y) that satisfy the elliptic curve equation together with the point O, known as the “point at infinity”. The “point at infinity” does not satisfy the elliptic curve equation. The coordinates x and y of the elliptic curve points are elements of the field GF(q), where q=pm and p is prime.
Equations (1) and (2) define the elliptic curve equations for the fields GF(p) and CF(2m), respectively:y2=x3+ax+b  (1)where a,bεGF(p) and 4a+27b2≠0(mod p); andy2=xy=x3+ax2+b  (2)where a,bεGF(2m) and b≠0.
The set of discrete points on an elliptic curve form an abelian group (commutative group), whose group operation is known as point addition. Bounds for the number of discrete points n on an elliptic curve over a finite field GF(q) are defined by Hasse's theorem, given in Equation (3), where the symbol n represents the number of points on the elliptic curve and where q=pm represents the number of elements in the underlying finite field.q+1−2√{square root over (q)}≦n≦q+1+2√{square root over (q)}  (3)
Elliptic curve “point addition” is defined according to the “chord-tangent process”. Point addition over GF(p) is described as follows.
Let P and Q be two distinct points on an elliptic curve E defined over the real numbers with Q≠−P (Q is not the additive inverse of P). The addition of P and Q is the point R (R=P+Q) where R is the additive inverse of S, and S is a third point on the elliptic curve intercepted by the straight line through points P and Q. For the curve under consideration, R is the reflection of the point S with respect to the x-axis, that is, if R is the point (x, y), S is the point (x, −y). The addition operation just described is illustrated in FIG. 2.
When P=Q and P≠−P, the addition of P and Q is the point R (R=2P) where R is the additive inverse of S, and S is the third point on the elliptic curve intercepted by the straight line tangent to the curve at point P. This operation is referred to as “point doubling,” and is shown in FIG. 3.
The “point at infinity”, O, is the additive identity of the group. The most relevant operations involving O are the following: the addition of a point P and O is equal to P(P+O=P); and the addition of a point P and its additive inverse, −P, is equal to O (P−P=O). If P is a point on the curve, then −P is also a point on the curve.
The point operation used by elliptic curve cryptosystems is referred to as point multiplication. This operation is also referred to as scalar point multiplication. The point multiplication operation is denoted as kP, where k is an integer number and P is point on the elliptic curve. The operation kP represents the addition of k copies of point P, as shown in Equation (4).
                    kP        =                              P            +            P            +            …            +            P                                ︸                          k              ⁢                                                          ⁢              times              ⁢                                                          ⁢              P                                                          (        4        )            
Elliptic curve cryptosystems are built over cyclic groups. Each group contains a finite number of points, n, that can be represented as scalar multiples of a generator point: iP for i=0, 1, . . . , n−1, where P is a generator of the group. The order of point P is n, which implies that nP=O and iP≠O for 1<i<n−1. The order of each point on the group must divide n. Consequently, a point multiplication kQ for k>n can be computed as (k mod n)Q.
Scalar multiplication is the basic operation for ECC. Scalar multiplication in the group of points of an elliptic curve is the analogue of exponentiation in the multiplicative group of integers modulo a fixed integer m. Computing kP can be performed using a straightforward double-and-add approach based on the binary representation of k=ki-1, . . . , k0 where ki-1 is the most significant bit of k. Other scalar multiplication methods have been proposed in the literature.
One of the simplest scalar multiplication algorithms is the double-and-add point multiplication algorithm, which is the so-called binary algorithm. Algorithms 1 and 2 show the most-to-least and the least-to-most versions of the double-and-add scalar multiplication algorithms, respectively. The algorithms inspect the multiplier k. For each inspected bit, the algorithms perform a point double, and if the inspected bit is one, the algorithms also perform a point add.
Algorithm 1: Double-and-Add (most-to-least)Inputs: P,kOutput: kPInitialization:  Q = PScalar Multiplication:  for i = l−2 down to 0 do    Q = 2Q    if ki = 1 then Q = Q + P  end forreturn(Q)
Algorithm 2: Double-and-Add (least-to-most)Inputs: P,kOutput: kPInitialization:  Q = O, R = PScalar Multiplication:  for i = 0 to l−1 do    if ki = 1 then Q = Q + R    R = 2R  end forreturn(Q)
The double-and-add scalar multiplication algorithms require, on average, l point doubles and l/2 point additions, where l≈|log2 k|. These algorithms also require the storage of two points, P and Q.
The security of an elliptic curve cryptosystem may be compromised by a power analysis attack. Power analysis attacks may be a particular problem for portable devices, such as smart cards, that draw their power supply from an external source. The cryptographic system in such devices is generally implemented with semiconductors, and the current drawn by the semiconductors continuously changes when performing the computations and other operations involved in implementing the cryptographic algorithms. By placing a resistor in series with the power supply and using an oscilloscope to measure the voltage drop across the resistor, the changes in current and therefore power consumption during each clock cycle can be measured and plotted to obtain a power trace. The power traces may reveal information about the instructions being executed and the contents of the data registers, making it possible to deduce the secret key.
Power analysis attacks are usually divided into two types. The first type, Simple Power Analysis (SPA), may be based on a single observation of power consumption, while the second type, Differential Power Analysis (DPA), combines SPA attack with an error-correcting technique using statistical analysis over multiple observations of power consumption. More importantly, classical DPA attacks have been extensively researched for each cryptosystem, and new types of DPA are continuously being developed. Many of the existing countermeasures are vulnerable to the more recent attacks, which include Refined Power Analysis (RPA), Zero Power Analysis (ZPA), Doubling Attack, and Address-Bit Differential Power Analysis (ADPA).
An SPA attack may consist of observing the power consumption during a single execution of a cryptographic algorithm. The operations involved in elliptic curve point addition and elliptic curve point doubling produce distinctive power traces that can be readily distinguished upon simple visual observation. The power consumption analysis may also enable one to distinguish between point addition and point doubling in the double-and-add algorithm. The sequence of the point addition and point doubling operations may enable the attacker to determine the individual bits of the secret key k in the scalar multiplication kP, from which the public key may be easily deduced.
Coron showed that, for Algorithm 1 to be SPA resistant, the instructions performed during a cryptographic algorithm should not depend on the data being processed, there should not be any branch instructions conditioned by the data, etc. This could be done by performing the addition and doubling each time and then, at the end of the loop, decide whether to accept the result or to eliminate the addition part according to value of k, (see Algorithms 3 and 4). However, even though this scheme is resistant to a SPA attack, it remains vulnerable to a DPA attack.
Algorithm 3: Double-and-Add Always (most-to-least)Input P, kQ[0] ← Pfor i from l− 2 to 0 do  Q[0] ← 2Q[0]  Q[1] ← Q[0] + P  Q[0] ← Q[ki]output Q[0]
Algorithm 4: Double-and-Add Always (least-to-most)Input P, kQ[0] ← PQ[1] ← Ofor i from 0 to l− 1 do  Q[2] ← Q[0] + Q[1]  Q[0] ← 2Q[0]  Q[1] ← Q[1 + ki]output Q[1]
A DPA attack is based on the same basic concept as an SPA attack, but uses error correction techniques and statistical analysis to extract very small differences in the power consumption signals. To be resistant to a DPA attack, some system parameters or computation procedures must be randomized.
Coron suggested three countermeasures to protect against DPA. The first countermeasure is randomization of the private exponent, as follows. Let #E be the number of points of the curve. The computation of Q=kP is done by: selecting a random tri-bit number d; computing k′=k+d#E; and computing the point Q=k′P. Thus, Q=kP, since #EP=O.
The second countermeasure is blinding point P. The point P to be multiplied is “blinded” by adding a secret random point R for which we know S=kR. Scalar multiplication is done by computing the point k(R+P) and subtracting S=kR to get Q=kP.
The third countermeasure is randomizing projective coordinates. The projective coordinates of a point are not unique because:(X,Y,Z)=(λX,λY,λZ)  (5)for every λ≠0 in the finite field. The third countermeasure randomizes the projective coordinate representation of a point P=(X,Y,Z). Before each new execution of the scalar multiplication algorithm for computing Q=kP, the projective coordinates of P are randomized with a random value λ. The randomization can also occur after each point addition and doubling.
An enhanced version of Coron's third countermeasure has been proposed by Joye and Tymen. It uses an isomorphism of an elliptic curve, thereby transposing the computation into another curve through a random morphism. The elliptic point P=(X,Y,Z) and parameters (a, b) of the defined curve equation can be randomized, e.g., to (λ2X,λ3Y,Z) and (λ4a,λ6b), respectively. However, all of the above countermeasures add computational overhead and are still vulnerable to differential power attacks, as described below.
The doubling attack obtains the secret scalar using binary elliptic scalar multiplication. It only works for the most-to-least version of the double-and-add algorithm. The main idea of this attack is based on the fact that, even if an adversary cannot see whether the computation being done is doubling or addition, he can still detect when the same operation is done twice. More precisely, if 2A and 2B are computed in any operations, the attacker is not able to guess the value of A or B but he can check if A=B or A≠B. This assumption is reasonable, since this kind of computation usually takes many clock cycles and depends greatly on the value of the operands. If the noise is negligible, a simple comparison of the two power traces during the doubling will be efficient to detect this equality.
Two of Coron's three proposed countermeasures against DPA attacks fail to protect against a doubling attack, viz., randomizing the private scalar (exponent) and blinding the point. However, his third countermeasure, the randomized projective coordinate does protect against a doubling attack, as does a randomized exponentiation algorithm, such as the Ha and Moon algorithm, which maps a given scalar to one of various representations. Since the positions of the zeros in the Ha and Moon algorithm vary in each representation, the doubling attack cannot detect the positions of the zeros for the doubling operation.
Basically, to protect against a doubling attack, the random blinding point R should be randomly updated. A regularly updated method should not be chosen. A method similar to Coron's third countermeasure or a random field isomorphism should be used.
Goubin proposed a new power analysis in 2003, namely, the Refined Power Analysis (RPA), which works even if one of the three countermeasures with an SPA countermeasure is applied. The RPA attack assumes that the attacker can input adaptively chosen messages or elliptic curve points to the victim exponentiation algorithm. Smart analyzed the RPA attack in detail and discounted its effectiveness in a large number of cases. For the remaining cases, Smart proposed a defense against the RPA attack based on isogenies of small degree. However, the RPA attack is still a threat to most elliptic curve cryptosystems.
The Zero-value Point Attack (ZPA) is an extension of the RPA attack. In an RPA attack, the attacker uses a special point, which has a zero-value coordinate. In a ZPA attack, on the other hand, an attacker utilizes an auxiliary register, which might take a zero-value in the definition field. As a result, Coron's third or random field isomorphism countermeasures do not protect against ZPA attacks.
To protect against RPA and ZPA attacks, the base point P or the secret scalar k should be randomized. For example, Coron's first two countermeasures protect against these attacks. Mamiya et al. recently proposed a countermeasure called BRIP, which uses a random initial point R. The proposed countermeasure computes kP+R and then subtracts R to get kP. Thus, no special point or zero-value register will appear during all operations and, hence, it is resistant against both RPA and ZPA attacks.
In 1999, Messerges et. al. proposed a new attack against secret key cryptosystems, the address-bit DPA (ADPA), which analyzes a correlation between the secret information and the addresses of registers. Itoh et. al., in 2002, extended this attack to Elliptic Curve-based Cryptosystems. Basically, the ADPA Attack is based on the correlation between bit values of the scalar and the location (address) of the variables used in a scalar multiplication algorithm. Countermeasures used to protect against simple power analysis and differential power analysis that are based on randomization of the base point or the projective coordinate do not provide countermeasures against address-bit analysis attacks. Therefore, these countermeasures do not remove the correlation between the bit values of a scalar and the location (address) of the variables used in a scalar multiplication algorithm.
A hardware-based DPA countermeasure proposed by May et. al. is based on Randomized Register Renaming (RRR). RRR is supposed to be implemented on a processor called NDISC, which can execute instructions in parallel. In other words, it requires special hardware to work. Itoh et al. also has proposed several countermeasures against the ADPA attack, but those countermeasures double the computing time.
In 2003, Itoh et al. proposed a countermeasure called the Randomized Addressing method (RA), which is similar to RRR but does not require special hardware. In RA, the addresses of registers are randomized by a random number for each scalar exponentiation. Thus, all addresses of registers are randomized and, hence, the side channel information is also randomized.
However, none of theses approaches, taken either singly or in combination, is seen to describe the instant invention as claimed. Thus, a method for elliptic curve scalar multiplication solving the aforementioned problem's is desired.